\section{Evaluation}
\label{sec:eval}
In this section, we evaluate the effectiveness
of the proposed MobiTrack
on real-world datasets.
We implement the mechanism in Python
and make comparisons about its performance
with various benchmarks.

\subsection{Dataset Overview}
Two datasets used in experiments will be described briefly in the chapter.
\begin{figure}
    %\vspace{-0.8cm}  %璋冩暣鍥剧墖涓庝笂鏂囩殑鍨傜洿璺濈
      \setlength{\abovecaptionskip}{0.1cm}   % 璋冩暣鍥剧墖鏍囬涓庡浘璺濈
      \setlength{\belowcaptionskip}{-0.6cm}   % 璋冩暣鍥剧墖鏍囬涓庝笅鏂囪窛绂?
       \begin{minipage}{0.43\linewidth}
     \centerline{\includegraphics[width=0.6\textwidth]{fig/roma_part2.png}}
     \centerline{\small{(a)  20 million raw GPS points in Rome}}
    %  \caption{Prediction Accuracy.}
    % \label{fig:pred_res}
       \end{minipage}
         \hfill
          \begin{minipage}{0.525\linewidth}
        \centerline{\includegraphics[width=0.8\textwidth]{fig/heatmap_rome.png}}
        \centerline{\small{(b) The Density of Check-ins in Rome}}
        \end{minipage}
        \caption{The Experimental Datasets.}
        \label{fig:gps_loc}
\end{figure}

\textbf{Rome Taxi Dataset:}
the experimental data for movement prediction we used
were collected from real-world mobility traces
of taxi cabs in Rome, Italy~\cite{romataxi}.
The roma taxi dataset contains about 20 million GPS points
of approximately 320 taxis collected over 30 days (as shown in Fig.~\ref{fig:gps_loc}(a)).
Each GPS point consists of
a taxi ID, a timestamp, a longitude and a latitude,
collected every 15 seconds.

\textbf{Rome Check-ins Dataset:}
we use the Rome check-ins dataset extracted from Foursquare in
\cite{yang2015nationtelescope,yang2015participatory},
which includes long-term
(about 18 months)
global-scale check-in data in 415 cities in 77 countries
from April 2012 to September 2013,
to evaluate the task assignment performance
of the proposed mechanism.
The data of Rome contains 42574 check-ins and
The density of check-ins in 18 months
is shown in fig.~\ref{fig:gps_loc}(b).
Obviously, most of the check-ins
are distributed in the central urban area,
i.e., within longitude (12.447, 12.512) and latitude (41.8957, 41.9112).
Thus, we create the tasks in these areas
and check-in users in these areas can be seen as the workers.

\subsection{Simulation Setup}
\subsubsection{Movement Prediction}
As the GPS points of different vehicles in Rome Taxi Dataset are mixed,
we apply an aggregation algorithm by using
the attributes {\it taxi ID} and {\it timestamp}
to aggregate sequences of GPS points for each taxi.
Considering that the stay time indicates whether a trip is terminated or not,
we use the GPS points that vehicles stay beyond 120 seconds
to split the data into trajectories.
Therefore, we obtain a trajectory dataset,
10,000 trajectories are randomly picked from
this dataset as the testing set, the remains is used
as training set to construct the $N$-Gram model.

Two metrics are utilized to evaluate the effectiveness of
the proposed movement prediction mechanism:
the prediction accuracy (Acc) and tracking coverage (TC).
\begin{itemize}
    \item[1)] Acc: For each trajectory
    $Tr_i=\{l_{i1}, l_{l2}, \cdots \}$
    in the testing set,
    there are $|Tr_i \vert $ locations,
    and for each location in $Tr_i$ except the last one,
    we can predict the most probable movement with the
    constructed $N$-Gram model.
    The Acc is the total number of predictions divided by
    the number of correct predictions.
    \item[2)] TC: given the number of sensing locations $k$,
    the ratio of the number of successfully tracked tasks
    that satisfy a certain tracking rate (see Definition~\ref{def:Tkrate})
    to the number of total tasks.
\end{itemize}

In order to evaluate the effectiveness of $N$-Gram-C,
we compare our method with existing movement prediction algorithms.
Particularly,
another grid-based MMC prediction algorithm,
i.e., $N$-MPRE~\cite{JingGWLLY18},
which employs a grid representation of
the data space including the urban space 
and incorporates n previous visited grids
of the object for next movement prediction,
is used as the baseline.
We set the side length of the grid as 100 m.
% \begin{itemize}
%     \item $N$-MPRE~\cite{JingGWLLY18}:
%     The grid-based MMC prediction algorithm
%     which employs a grid representation of
%     the data space including the urban space,
%     and incorporates n previous visited grids
%     of the object for next movement prediction.
%     We set the side length of the grid as 100 m.
%     \item 
% \end{itemize}

\subsubsection{Task Assignment}
We set the positions of tasks based on the locations
learned by a variant of the k-means clustering algorithm
(see Section~\ref{subsec:off_pred}),
and the positions of workers are set based on
the leisure places, e.g., hotel, rest and coffee,
of users in the Rome Check-ins Dataset.
There are 447 learned locations 
and 1125 checked-in leisure places
in the central urban area of Rome.

In the experiments, we randomly select a certain number of
learned locations as the position of tasks
and leisure places as the position of workers.
Specifically, to scale down the task assignment problem,
the number of tasks is set as 50, and the number of workers
is set from 100 to 500.
For the calculation of the system utility in equation~\ref{eq:utility},
we set the tracking task benefit $M$ to 100,
the exponent $\gamma$ to 1,
and the movement probability $p(l|f)$ is set according to
the belonged ongoing trip $f$ of $l$
and $N$-Gram-C prediction model.
Furthermore, To meet the time constraint,
we assume that
the average moving speed of a worker is 200 m/min and
the average speed of a vehicle is 30 km/h.

For comparison, three performance metrics,
including the system cost, system benefit and system utility,
are adopted, which are defined in Section~\ref{subsec:sys_model}.

In order to simulate workers' behaviors in real world,
we use the following benchmarks.
\begin{itemize}
  \item \textbf{Nearest Location First (NLF).}
  NLF is a greedy strategy to select the closest sensing
  task for each worker, which aims to minimize the system cost
  while ignoring the system benefit.
  \item \textbf{Most Probable Location First (MPLF).}
  MPLF is also a greedy strategy but selecting the task with the highest payment for each worker.
  \item \textbf{People-Centric Selection (PCS)~\cite{JingGWLLY18}.}
  Each worker randomly selects a sensing task within
  the time constraint, to conduct the tracking task without
  considering any system performance.
%  \item \textbf{Most Benefit Nearest Worker Selection (MBNWS).} MBNWS is a greedy strategy to assign the
%      closest worker to the most possible location, thus
%      achieve the maximum utility.
\end{itemize}

